⟸ Go Back ⟸
Exercise 13 (Homework 2).
(regular languages, arithmetic progressions, hard exercise, base-2, unary)

Arithmetic progressions are regular

Let \boldsymbol{a}=(a_1,a_2,\dots) be an arithmetic progression, i.e. a sequence in which the difference between any two consecutive terms is a constant. The goal of this exercise is (somewhat informally) to show that regardless of the base chosen to represent the arithmetic progression, this gives rise to a regular language.

More precisely:

  1. Show that the language \{1^m \mid m\in \boldsymbol{a}\} is regular.

  2. Given n\in \mathbb N, how many states does the minum DFA recognizing \{1^m \mid m\in n\mathbb N\} have?

  3. Show that the language \{w\in \{0,1\}^* \mid \mathtt{value}_2(w)\in \boldsymbol{a}\} is regular.

  4. Given n\in \mathbb N, how many states does the minimum DFA recognizing \{w\in\{0,1\}^* \mid \mathtt{value}_2(w)\in n\mathbb{N}\} have when n=2^k for some k\in \mathbb N? What about when n is odd? What about when n=m2^k for some k\in \mathbb N and m is odd?

  5. Show that the language \{w\in \{0,1,2\}^* \mid \mathtt{value}_3(w)\in \boldsymbol{a}\} is regular.

  6. Show that the language \{w\in \Sigma^* \mid \mathtt{value}_b(w)\in \boldsymbol{a}\} is regular, where b \ge 2 and \Sigma=\{0,1,2,\dots,b-1\} is an alphabet of digits.

Remember that, for any b \ge 2, \mathtt{value}_b(w) denotes the number obtained interpreting the string w as a number written using base b. For instance, \mathtt{value}_2(00101)=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+0\cdot 2^3+0\cdot 2^4=1+4=5, \mathtt{value}_3(0121)=1\cdot 3^0+2\cdot 3^1+1\cdot 3^2+0\cdot 3^3=1+6+9=16.